package com.sunny.example.dfs;

import java.util.*;

/**
 * 最长连续子串
 */
public class Dfs0102 {
    public static List<Integer> lenList = new ArrayList<>();

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            lenList.clear();
            String str1 = "";
            int sum = 0;
            String[] subInts = null;
            for (int i = 2; i > 0; i--) {
                if (i == 2) {
                    str1 = scanner.nextLine();
                    subInts = str1.split(",");
                } else {
                    sum = Integer.parseInt(scanner.nextLine());
                }
            }
            if (subInts == null || subInts.length == 0) {
                continue;
            }

            for (int j = 0; j < subInts.length - 1; j++) {
                int initValue = Integer.parseInt(subInts[j]);
                int initIndex = j + 1;
                //利用递归
                calcuSubStr(initValue, initIndex, subInts, sum, 1);
            }

            lenList.sort(new Comparator<Integer>() {
                @Override
                public int compare(Integer o1, Integer o2) {
                    return o2 == o1 ? 0 : o2 > o1 ? 1 : -1;
                }
            });

            if (lenList.size() > 0)
                System.out.println(lenList.get(0) + 1);

        }
    }

    private static void calcuSubStr(int initValue, int initIndex, String[] subInts, int sum, int recycle) {
        if (recycle >= subInts.length){
            //当深度已经达到输入数据的长度时，返回
            return;
        }
        for (int k = initIndex; k < subInts.length; k++) {
            initValue += Integer.parseInt(subInts[k]);
            if (initValue == sum) {
                //方法一：使用List把所有长度放入一个数组中，待排序
                if (!lenList.contains(recycle)) {
                    lenList.add(recycle);
                }
                continue;
            }
            calcuSubStr(initValue, initIndex + 1, subInts, sum, recycle + 1);

        }
    }
}
